/*
 * @lc app=leetcode.cn id=1201 lang=typescript
 *
 * [1201] 丑数 III
 */

// @lc code=start
// 通过二分查找
function nthUglyNumber(n: number, a: number, b: number, c: number): number {
  // 最大公约数
  const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
  // 最小公倍数
  const lcm = (a: number, b: number): number => (a * b) / gcd(a, b);
  // 找到第x个丑数
  const find = (x: number): number => {
    let ab = lcm(a, b);
    let ac = lcm(a, c);
    let bc = lcm(b, c);
    let abc = lcm(a, lcm(b, c));
    return (
      Math.floor(x / a) +
      Math.floor(x / b) +
      Math.floor(x / c) -
      Math.floor(x / ab) -
      Math.floor(x / ac) -
      Math.floor(x / bc) +
      Math.floor(x / abc)
    );
  };

  let l = 1;
  let r = n * Math.min(a, b, c);
  let mid: number;
  // 二分查找区间范围内有几个丑数
  // 如果区间范围内有几个丑数等于n，则区间范围内的丑数就是第n个丑数
  while (l < r) {
    mid = l + Math.floor((r - l) / 2);

    if (find(mid) < n) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }

  return l;
}
// @lc code=end
